# -*- coding: utf-8 -*-
"""
@author:  yinbing.li(yinbing.li@zillnk.com)
@version: 1.0.0
@file:    leetcode695_岛屿的最大面积.py
@time:    2023/3/8 15:35
"""
import collections
from typing import List


class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        _max = 0
        for i in range(len(grid)):
            for k in range(len(grid[0])):
                _max = max(_max, self.dfs(i, k, grid))
        return _max

    def dfs(self, r, c, grid: List[List[int]]):
        if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]) or grid[r][c] == 0:
            return 0
        grid[r][c] = 0
        return 1 + self.dfs(r - 1, c, grid) + self.dfs(r + 1, c, grid) + \
            self.dfs(r, c - 1, grid) + self.dfs(r, c + 1, grid)

    # ================================以下为广度搜索算法解法==========================================
    def maxAreaOfIslandWithBFS(self, grid: List[List[int]]) -> int:
        _max = 0
        for i in range(len(grid)):
            for k in range(len(grid[0])):
                if grid[i][k] == 1:
                    no = 1
                    queue = collections.deque()
                    queue.appendleft((i, k))
                    grid[i][k] = 0
                    while len(queue) != 0:
                        r, c = queue.pop()
                        dirs = [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]
                        for d in dirs:
                            if 0 <= d[0] < len(grid) and 0 <= d[1] < len(grid[0]) and grid[d[0]][d[1]] == 1:
                                queue.appendleft(d)
                                grid[d[0]][d[1]] = 0
                                no += 1
                    _max = max(no, _max)
        return _max
